package course2;

public class SinglyList<T> extends Object
{
    private Node<T> head;
    private SinglyList()//构造空单链表
    {
        this.head=new Node<>();//构造头节点，data和next值均为null
    }
    private SinglyList(T[] values)//构造单链表，由values数组提供元素
    {
        this();//构造空单链表，只有头结点
        Node<T>rear=this.head;//rear指向单链表最后一个结点
        for(int i=0;i<values.length;i++)//若values.length==0,构造空链表
        {
            rear.next=new Node<T>(values[i],null);//尾插入，创建节点链入rear结点之后
            rear=rear.next;//rear指向新的结点
        }
    }
    public boolean isEmpty()//判断单链表是否为空
    {
        return this.head.next==null;
    }
    private T get(int i)//返回第i个元素，i小于表长度，i越界则返回null
    {
        Node<T>p=this.head.next;
        for(int j=0;p!=null&&j<i;j++)//遍历单链表，寻找第i个结点（p指向）
            p=p.next;
        return (i>=0&&p!=null)? p.data:null;//若p指向第i个结点，返回其元素值
    }
    private void set(int i,T x)//返回第i个元素，i小于表长度，x!=null。
    {
        Node<T>p=this.head.next;
        for(int j=0;p!=null&&j<i;j++)//遍历单链表，寻找第i个结点（p指向）
            p=p.next;
        p.data=x;//设置第i个元素值为x
    }
    private int size()//返回单链表长度，O(n)
    {
        int i=0;
        for( Node<T> p=this.head.next;p!=null; i++)
            p=p.next;
        return i;
    }
    public String toString()
    {
        String str="list：(";//返回类名
        for(Node<T>p=this.head.next;p!=null;p=p.next)//p遍历单链表
        {
            str+=p.data.toString();
            if(p.next!=null)
                str+=",";//不是最后一个结点，加分隔符
        }
        return str+")";//空表返回()
    }
    private Node<T>insert(int i,T x)//插入x作为第i个元素，x!=null,返回头结点
    {
        if (x==null)
            throw new NullPointerException("x==null");//抛出空对象异常
        Node<T>front=this.head;//front指向头结点
        for(int j=0;front.next!=null&&j<i;j++)//寻找第i-1个或最后一个结点(front指向)
            front=front.next;
        front.next=new Node<>(x,front.next);//在front之后插入值为x的结点
        return front.next;//返回插入结点
    }
    public Node<T>insert(T x)//单链表尾添加x对象，O(n)
    {
        //调用insert(i,x),用整数最大值指定插入在最后，遍历一次，i必须容错
        return insert(Integer.MAX_VALUE,x);
    }
    private T remove(int i)//删除第i个元素，i小于n，若i越界，则返回null
    {
        Node<T>front=this.head;//front指向头结点
        for(int j=0;front.next!=null&&j<i;j++)//遍历寻找第i-1个结点(front指向)
            front=front.next;
        if(i>=0&&front.next!=null)//若front后继结点存在，则删除
        {
            T old=front.next.data;//获得删除结点引用的对象
            front.next=front.next.next;//删除front的后继，包括头，中间，尾部删除
            return old;//返回被删除的内容
        }
        return null;//若i<0或i大于表长
    }
    //删除对应子表(原创)★
    private SinglyList<T> remove(int begin,int end)
    {
        if(begin<=0&&end>=this.size()-1)//容错,减少时间和空间复杂度
            clear();//删除所有子表
        else if (begin>=this.size()-1) //容错,减少时间和空间复杂度
            return null;
        else
        {
            Node<T>front=this.head;//front指向头结点
            Node<T>behind=this.head;//behind指向头结点
            for(int j=0;front.next!=null&&j<begin;j++)//遍历寻找第begin-1个结点
                front=front.next;
            for(int j=0;behind.next!=null&&j<=end;j++)//寻找第end个结点
                behind=behind.next;
            if(begin>=0&&end>=0&&front.next!=null&&behind.next!=null)
                front.next=behind.next;
        }
        return null;
    }
    //删除所有子表(原创)★★
    private void removeAll(SinglyList<T> pattern)
    {
        Node<T>r=pattern.head.next;
        Node<T>p;
        //大循环,p用来找和pattern第一个元素相同的元素
        //r指向pattern的第一个元素,每次循环都更新
        for(p=this.head;p.next!=null;p=p.next)
        {
            if(p.next.data==r.data)
            {
                Node<T>q;
                //q用来比对和r数值是否相等
                //r指向pattern的后继结点
                for(q=p.next;q.next!=null&&r.next!=null;q=q.next,r=r.next)
                    if(!q.data.equals(r.data))
                        break;
                //如果循环没有被break终止，并且q和r指向的最后一个元素相等
                if(r.next==null&&r.data==q.data)
                    p.next=q.next;
                r=pattern.head.next;//r要回到起点★★★
            }
        }
    }
    //替换所有子表(原创)★★★
    private void replaceAll(SinglyList<T> pattern, SinglyList<T> list)
    {
        Node<T>r=pattern.head.next;
        Node<T>p;
        //大循环,p用来找和pattern第一个元素相同的元素的前面元素
        //r指向pattern的第一个元素,每次循环都更新
        for(p=this.head;p.next!=null;p=p.next)
        {
            if(p.next.data==r.data)
            {
                Node<T>q;
                //q用来比对和r数值是否相等
                //r指向pattern的后继结点
                for(q=p.next;q.next!=null&&r.next!=null;q=q.next,r=r.next)
                    if(!q.data.equals(r.data))
                        break;
                //如果循环没有被break终止，并且q和r指向的最后一个元素相等
                if(r.next==null&&r.data==q.data)
                {
                    SinglyList<T>list2=new SinglyList<T>(list);//深拷贝list2=list
                    Node<T>s=list2.head;
                    while(s.next!=null)
                        s=s.next;//s指向list2的末尾
                    s.next=q.next;
                    p.next=list2.head.next;
                }
                r=pattern.head.next;//r要回到起点★★★
            }
        }
    }
    private void clear()
    {
        this.head.next=null;//Java自动回收所有结点占用的存储空间
    }
    private Node<T> search(T key)
    {
        for (Node<T> p=this.head.next;  p!=null;  p=p.next)
            if (key.equals(p.data))
                return p;
        return null;
    }
    public boolean contains(T key)
    {
        return this.search(key)!=null;
    }
    public Node<T> insertDifferent(T x)
    {
        Node<T> front=this.head, p=front.next;
        while (p!=null && !p.data.equals(x))
        {
            front = p;
            p = p.next;
        }
        if (p!=null)
        {
            System.out.println("x="+x+"元素重复，没有插入");
            return p;
        }
        return front.next = new Node<>(x,null);
    }
    public T remove(T key)
    {
        Node<T> front=this.head, p=front.next;
        while (p!=null && !key.equals(p.data))
        {
            front = p;
            p=p.next;
        }
        if (p!=null)
        {
            front.next = p.next;
            return p.data;
        }
        return null;
    }
    private static SinglyList<String> reverse(SinglyList<String>list)
    {//单链表反转
        Node<String> p=list.head.next;
        Node<String>succ=null;
        Node<String>front=null;
        while (p!=null)
        {
            succ=p.next;
            p.next=front;
            front=p;
            p=succ;
        }
        list.head.next=front;
        return list;
    }
    private SinglyList(SinglyList<T> list)
    {
        //深拷贝构造方法，复制单链表list的所有结点
        this();                                     //创建空单链表，只有头结点
        Node<T> rear=this.head;
        for (Node<T> p=list.head.next; p!=null; p=p.next)  //p遍历list单链表
        {
            rear.next = new Node<>(p.data, null); //复制结点尾插入
            rear = rear.next;                             //指向this单链表尾
        }
    }
    public boolean equals(Object obj)
    {
        //比较两条单链表是否相等，覆盖Object类的equals方法
        if (obj == this)
            return true;
        if (!(obj instanceof SinglyList<?>))
            return false;
        Node<T> p=this.head.next;
        @SuppressWarnings("unchecked")
        Node<T> q=((SinglyList<T>)obj).head.next;
        while (p!=null && q!=null && p.data.equals(q.data))
        {
            p=p.next;
            q=q.next;
        }
        return p==null && q==null;
    }
    public static void main(String [] args)
    {
        String   [] values={"1","2","3","4","5","6","7","8","9"};
        Integer []values1={1,2,3,4,5,6,7,8,9};
        SinglyList<String>list=new SinglyList<>(values);
        SinglyList<Integer>listb=new SinglyList<>(values1);
        SinglyList<Integer>liste=new SinglyList<>(listb);
        System.out.println(list);
        list.remove(5);
        System.out.println(list);
        System.out.println("反序输出"+reverse(list));
        System.out.println(list.search("4"));
        list.insert(3,"9");System.out.println(list);
        System.out.println(list.get(4));
        System.out.println(list.size());
        System.out.println(listb);
        liste.set(0, 22);System.out.println("改变liste后liste值为"+liste);
        System.out.println("改变liste后listb值为"+listb);
        System.out.println(liste.equals(listb));
        System.out.println(listb+"为删除子表前的listb");
        listb.remove(0,4);System.out.println(listb+"为删除子表后的listb");
        listb.clear();
        System.out.println("删除清空listb  是否为空"+listb.isEmpty());
        String []values3={"1","2","3","4","5","6","7","8","3","6",
                "6","7","8","9","6","1","6","7","9","0"};
        String []values4={"6","7","8"}; String []values5={"0","0","0"};
        SinglyList<String>listf=new SinglyList<>(values3);
        SinglyList<String>listg=new SinglyList<>(values4);
        SinglyList<String>listh=new SinglyList<>(values5);
        System.out.println("被替换下的子表为："+listg);
        System.out.println("被替换上的子表为："+listh);
        System.out.println("替换所有子表前："+listf);
        listf.replaceAll(listg, listh);
        System.out.println("替换所有子表后："+listf);
        listf.removeAll(listh);
        System.out.println("删除所有子表后："+listf);
    }
}